{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Blending Craft Beer\n", "\n", "## Try me\n", " [![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/CLP/solved/Blending%20Craft%20Beer%20(Solved%20CBC).ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FCLP%2Fsolved%2FBlending%20Craft%20Beer%20(Solved%20CBC).ipynb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction ##\n", "In this notebook we will use: \n", "\n", "- The Python open source Linear Programming library [PuLP](http://pythonhosted.org/PuLP/) to model and solve linear problems\n", "- The Python open source data analysis library [Pandas] (https://pandas.pydata.org/) to show the results\n", "- The IPython model display [Display] (https://ipython.org/ipython-doc/3/api/generated/IPython.display.html) to format the output \n", "- The Python numpy library [Numpy] (http://www.numpy.org/) to perform basic operations. \n", "\n", "We wil learn how to model problems in a way that scales to hundreds or thousands of variables and how to get all valuable information from the results generated by PuLP." ] }, { "cell_type": "code", "source": [ "!pip install pulp\n", "!pip install pandas\n", "!pip install numpy" ], "metadata": { "collapsed": false }, "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Definition\n", "\n", "Duff Beer is an american brewerie that sells alcoholic beverages worldwide. Duff beer has a very large market share in the US. One of the new business lines of Duff Beer is in the craft beer sector. Duff beer buys 3 types of wort from local suppliers. The availability of wort (in liters) and the price for each of them is specified in Table 1. \n", "\n", "**Table 1:** daily availability and cost of worts\n", "\n", "| Wort| Availability (liters)| Cost (€cents/liter) | \n", "|----------|----------------------|------------------------|\n", "| Type 1 | 2500 | 120 |\n", "| Type 2 | 1200 | 095 |\n", "| Type 3 | 2000 | 150 |\n", "\n", "The blend of the three types of worts must comply with the following quality requirements: \n", "\n", "- For Beer Angels, no less than 60% of Type 3 and no more of 20% of Type 2. The price of one bottle of Beer Angel is 4.10€s/liter. \n", "\n", "- For Beer Beast, no less than 15% of Type 3 and no more than 60% of Type 2. The price of one bottle of Beer Beast is 2.80€s/liter.\n", "\n", "- For Beer Cactus, no more than 50% of type 2. The selling price is 2.45€/liter.\n", "\n", "**Write a linear program to find the most profitable blend of worts to elaborate the three kinds of beers**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Model\n", "### Indices\n", "We can define the following indices to express the problem in a compact form:\n", "\n", "- i: wort type $i \\in [1, 2, 3]$\n", "- j: Beer brand $j \\in [A, B, C]$ where A notes Angels, B notes Beast, and C notes Cactus\n", "\n", "### Decision variables\n", "The decision variables are: \n", "\n", "$x_{ij}$: Amount of wort of type i (1, 2, 3) in Beer j: A (Angels), B (Beast), C (Cactus), (ie i=[1,2,3], j=[A,B,C])\n", "\n", "\n", "### Objective Function\n", "The objective function is:\n", "\n", "$\\max z = \\sum_{i=1}^{3}\\sum_{j=A}^{C}(d_j - c_i)*x_{ij}$\n", "\n", "where $d_j$ is the selling price of a bottle of beer j and $c_i$ is the cost per liter of wort type i.\n", "\n", "$\\max z =4 10(x_{1A}+x_{2A}+x_{3A})+280(x_{1B}+x_{2B}+x_{3B})+245(x_{1C}+x_{2C}+x_{3C})-120(x_{1A}+x_{1B}+x_{1C})-95(x_{2A}+x_{2B}+x_{2C})-150(x_{3A}+x_{3B}+x_{3C})$\n", "\n", "$\\max z = 290x_{1A}+315x_{2A}+260x_{3A}+160x_{1B}+185x_{2B}+130x_{3B}+125x_{1C}+150x_{2C}+95x_{3C}$\n", "\n", "\n", "### Constraints\n", "Subject to the following constraints:\n", "\n", "**Availability constraints**\n", "The availability constraints can be expressed in a compact form as: \n", "\n", "$\\sum_jx_{ij} \\leq a_i \\forall i$ \n", "\n", "Where $a_i$ is the availability of wort type i:\n", "\n", "$x_{1A}+x_{1B}+x_{1C} \\leq 2500$ \n", "\n", "$x_{2A}+x_{2B}+x_{2C} \\leq 1200$\n", "\n", "$x_{3A}+x_{3B}+x_{3C} \\leq 2000$\n", "\n", "**Quality constraints**\n", "The proportion of a given type of wort i' in a type of beer j' can be expressed as:\n", "\n", "$\\frac{x_{i'j'}}{\\sum_i(x_{ij'})} \\forall i', j'$\n", "\n", "If we compare this to the minimum proportion $rmin_{i'j'}$ we obtain:\n", " \n", "$\\frac{x_{i'j'}}{\\sum_i(x_{ij'})} \\geq rmin_{i'j'} \\forall i', j'$\n", "\n", "Or \n", "\n", "$x_{i'j'} \\geq rmin_{i'j'}*\\sum_i(x_{ij'}) \\forall i', j'$\n", "\n", "If we take the denominator to the RHS.\n", "We can obtain a similar expression for the maximum proportion $rmax_{i'j'}$:\n", "\n", "$x_{i'j'} \\geq rmax_{i'j'}*\\sum_i(x_{ij'}) \\forall i', j'$\n", "\n", "From these expressions, we can derive the constraints for every type of beer: \n", "\n", "**Angels quality requirement constraints**\n", "\n", "$x_{3A} \\geq 0.6(x_{1A}+x_{2A}+x_{3A})$\n", "\n", "$x_{2A} \\leq 0.2(x_{1A}+x_{2A}+x_{3A})$\n", "\n", "Beast quality requirement constraints\n", "\n", "$x_{3B} \\geq 0.15(x_{1B}+x_{2B}+x_{3B})$\n", "\n", "$x_{2B} \\leq 0.6(x_{1B}+x_{2B}+x_{3B})$\n", "\n", "Cactus quality requirement constraints\n", "\n", "$x_{2C} \\leq 0.5(x_{1C}+x_{2C}+x_{3C})$\n", "\n", "\n", "\n" ] }, { "cell_type": "code", "metadata": { "scrolled": true }, "source": [ "import pandas as pd\n", "import numpy as np\n", "from IPython.display import display, Markdown\n", "import pulp\n", "# Instantiate our problem class\n", "model = pulp.LpProblem(\"Maximising profits for Duff Beer\", pulp.LpMaximize)\n", "worts = ['Type 1', 'Type 2', 'Type 3']\n", "beers = ['Angel', 'Beast', 'Cactus']\n", "\n", "variables = pulp.LpVariable.dicts(\"Quantity in liters\",\n", " ((i, j) for i in worts for j in beers),\n", " lowBound=0,\n", " cat='Continuous')\n", "price = [410, 280, 245]\n", "cost = [120, 95, 150]\n", "\n", "coefficients = [price[j]-cost[i] for j in range(len(price)) for i in range(len(cost))]\n", "\n", "# Objective Function\n", "model += (\n", " pulp.lpSum([\n", " ((price[j]-cost[i]) * variables[(worts[i], beers[j])]\n", " for i in range(len(worts)) for j in range(len(beers)))])\n", ")\n", "\n", "# Constraints\n", "model += pulp.lpSum([variables['Type 1', j] for j in beers]) <= 2500, \"Type 1 availability\" \n", "model += pulp.lpSum([variables['Type 2', j] for j in beers]) <= 1200, \"Type 2 availability\" \n", "model += pulp.lpSum([variables['Type 3', j] for j in beers]) <= 2000, \"Type 3 availability\"\n", "\n", "model += variables['Type 3', 'Angel']>=0.6*pulp.lpSum([variables[i,'Angel'] for i in worts]), \"Angel >=60% Type 3 requirement\"\n", "model += variables['Type 2', 'Angel']<=0.2*pulp.lpSum([variables[i,'Angel'] for i in worts]), \"Angel <=20% Type 2 requirement\"\n", "\n", "model += variables['Type 3', 'Beast']>=0.15*pulp.lpSum([variables[i,'Beast'] for i in worts]), \"Beast >=15% Type 3 requirement\"\n", "model += variables['Type 2', 'Beast']<=0.6*pulp.lpSum([variables[i,'Beast'] for i in worts]), \"Beast <=60% Type 2 requirement\"\n", "\n", "model += variables['Type 2', 'Cactus']<=0.5*pulp.lpSum([variables[i,'Angel'] for i in worts]), \"Cactus <=50% Type 2 requirement\"\n", "\n", "\n", "model.solve()\n", "pulp.LpStatus[model.status]\n", "\n", "total_profit = pulp.value(model.objective)\n", "display(Markdown(\"Total profit is %0.2f €\"%total_profit))\n", "\n", "display(Markdown(\"The following table shows the decision variables: \"))\n", "var_df = pd.DataFrame.from_dict(variables, orient=\"index\", \n", " columns = [\"Variables\"])\n", "\n", "# First we add the solution. We apply a lambda function to get only two decimals:\n", "var_df[\"Solution\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.varValue))\n", "# We do the same for the reduced cost:\n", "var_df[\"Reduced cost\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.dj))\n", "\n", "\n", "# We use the display function to represent the results:\n", "display(var_df)\n", "\n", "\n", "const_dict = dict(model.constraints)\n", "con_df = pd.DataFrame.from_records(list(const_dict.items()), exclude=[\"Expression\"], columns=[\"Constraint\", \"Expression\"])\n", "\n", "#We create a list of records from the dictionary and exclude the Expression to have a more compact solution. \n", "con_df = pd.DataFrame.from_records(list(const_dict.items()), exclude=[\"Expression\"], columns=[\"Constraint\", \"Expression\"])\n", "\n", "#Now we add columns for the solution, the slack and shadow price\n", "\n", "con_df[\"Right Hand Side\"] = con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(-const_dict[item].constant))\n", "con_df[\"Slack\"] = con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].slack))\n", "con_df[\"Shadow Price\"] = con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].pi))\n", "\n", "# And we display the results\n", "display(con_df)\n", "\n", "display(Markdown(\"The following table shows the constraints: \"))\n", "display(con_df)\n" ], "outputs": [], "execution_count": null }, { "cell_type": "code", "metadata": {}, "source": [], "outputs": [], "execution_count": null } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 1 }